#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int len;
    bool Dfs(vector<int>& matchsticks, int i, vector<int>& edge)
    {
        if (i == matchsticks.size())
        {
            return true;
        }
        for (int j = 0;j < 4;++j)
        {
            edge[j] += matchsticks[i];
            if (edge[j] <= len && Dfs(matchsticks, i + 1, edge))
            {
                return true;
            }
            edge[j] -= matchsticks[i];
        }
        return false;
    }
    bool makesquare(vector<int>& matchsticks)
    {
        int sum = 0;
        for (auto a : matchsticks)
        {
            sum += a;
        }
        if (sum % 4 != 0) return false;
        len = sum / 4;
        vector<int> edge(4, 0);
        sort(matchsticks.begin(), matchsticks.end(), greater<int>());
        //cout<<(edge[0]==edge[1])<<endl;
        //cout<<"length="<<SideLength<<endl;
        return Dfs(matchsticks, 0, edge);
    }
};